// Copyright (c) 2023 徐丞烨，王凯钦，宋析峰，杨崇新
// SPDX-License-Identifier: GPL-3.0-or-later

#include <bits/stdc++.h>

using namespace std;

class Graph
{
private:
    int n;     // 图的顶点数
    int **adj; // 邻接矩阵

public:
    Graph(istream &in); // 构造函数，从输入流in中读取邻接矩阵
    ~Graph();           // 析构函数，释放邻接矩阵的内存
    int tsp();          // TSP算法，计算最短哈密顿回路
};

Graph::Graph(istream &in)
{
    in >> n;            // 读取顶点数
    adj = new int *[n]; // 动态分配二维数组
    for (size_t i = 0; i < n; i++)
    {
        adj[i] = new int[n];
    }
    for (size_t i = 0; i < n; i++)
    {
        adj[i][i] = 0; // 对角线上的元素为0
        for (int j = i + 1; j < n; j++)
        {
            in >> adj[i][j];       // 读取邻接矩阵
            adj[j][i] = adj[i][j]; // 邻接矩阵是对称矩阵
        }
    }
}

Graph::~Graph()
{
    for (size_t i = 0; i < n; ++i)
        delete[] adj[i]; // 释放每一行的内存
    delete[] adj;        // 释放二维数组的内存
}

int Graph::tsp()
{
    int p[n]; // 存储顶点的排列
    for (int i = 0; i < n; ++i)
        p[i] = i;      // 初始化顶点的排列
    int min = INT_MAX; // 存储最短哈密顿回路的长度
    do
    {
        int sum = 0; // 存储当前排列的哈密顿回路的长度
        for (int i = 0; i < n - 1; ++i)
            sum += adj[p[i]][p[i + 1]]; // 计算当前排列的哈密顿回路的长度
        sum += adj[p[n - 1]][p[0]];     // 加上回路的最后一条边
        if (sum < min)
            min = sum;                    // 更新最短哈密顿回路的长度
    } while (next_permutation(p, p + n)); // 生成下一个排列
    return min;                           // 返回最短哈密顿回路的长度
}

int main()
{
    ifstream fin("graph.txt"); // 打开输入文件
    Graph g(fin);              // 创建图
    fin.close();               // 关闭输入文件
    cout << g.tsp() << endl;   // 计算最短哈密顿回路并输出
    return 0;
}